The present invention relates to the field of cache design, and more particularly to adaptively allocating memory to support a partitioned cache of multiple logical levels enabling the cache to be adaptive to multiple criteria thereby improving the performance of the cache.
A network server, e.g., file server, database server, web server, may be configured to receive a stream of requests from clients in a network system to read from or write to a particular logical drive in an array of logical drives such as a Redundant Array of Independent Logical drives (RAID). These requests may form what is commonly referred to as a xe2x80x9cworkloadxe2x80x9d for the network server. That is, a workload may refer to the requests that need to be serviced by the network server.
Typically, a server in a network system may comprise a network interface controller configured to interface the server with an array of logical drives, e.g., RAID, via adapters, e.g., RAID adapters, coupled to one or more logical drives in the array of logical drives. A server may be configured to create a cache in its main memory, e.g., Random Access Memory (RAM), to increase the speed of accessing data. A cache is faster than a logical drive and thereby allows data to be read at higher speeds. Thus, if data is stored in the cache it may be accessed at higher speeds than accessing the data on a logical drive.
There have been many methods in designing caches that seek to increase the cache hit rate thereby improving performance of the cache. A xe2x80x9ccache hitxe2x80x9d is said to occur if an item, e.g., data, requested by the processor in the server or a client in a network system, is present in the cache. When an item, e.g., data, requested by the processor in the server or a client in the network system, is not present in the cache, a xe2x80x9ccache missxe2x80x9d is said to occur. A xe2x80x9ccache hit ratexe2x80x9d may refer to the rate at which cache hits occur. By improving the cache hit rate, the performance of the system may be improved, i.e., less data needs to be serviced from the logical drive.
One method to improve the performance of a cache is commonly referred to as the Least Recently Used (LRU) replacement method as illustrated in FIG. 1. The LRU replacement method uses a single stack 101 comprising a set of cache entries where each cache entry stores particular data. As stated above, if an item, e.g., data, requested by the processor in the server or client in a network system is present in the cache, a xe2x80x9ccache hitxe2x80x9d is said to occur. When a cache hit occurs, the cache entry comprising the information, e.g., data, requested moves to the first stack position as illustrated in FIG. 1. As stated above, if an item, e.g., data, requested by the processor in the server or client in a network system is not present in the cache, a xe2x80x9ccache missxe2x80x9d is said to occur. When a cache miss occurs, the requested item is retrieved from the logical drive and then stored in the first stack position as illustrated in FIG. 1. When a new entry is inserted in stack 101, the cache entry in the last stack position of stack 101 is evicted. The information, e.g., data, may subsequently be discarded.
Another method to improve the performance of a logical drive cache is commonly referred to as the Segmented LRU (S-LRU) replacement method as illustrated in FIG. 2. The S-LRU replacement method may use two stacks 201A-B. Each stack, stack 201A-B, may comprise a set of cache entries where each cache entry stores particular data. When a cache hit occurs in the first stack, e.g., stack 201A, the cache entry comprising the information, e.g., data, requested moves up to the first stack position of the second stack, e.g., stack 201B, as illustrated in FIG. 2. When a new entry is added to stack 201B, the cache entry at the last stack position of stack 201B is evicted to the first stack position of stack 201A. When a new entry is inserted in stack 201A, the cache entry at the last stack position of stack 201A is evicted. The information, e.g., data, may subsequently be discarded. When a cache hit occurs in the second stack, e.g., stack 201B, the cache entry comprising the information, e.g., data, requested moves up to the first stack position of that stack, e.g., stack 201B, as illustrated in FIG. 2. When a new entry is inserted in stack 201B, the cache entry at the last stack position of stack 201B is evicted to the first stack position of stack 201A. When a new entry is inserted in stack 201A, the cache entry at the last stack position of stack 201A is evicted. When a cache miss occurs, the requested item is retrieved from the logical drive and then stored in the first stack position of the first stack, e.g., stack 201A, as illustrated in FIG. 2. When a new entry is inserted in stack 201A, the cache entry at the last stack position of stack 201A is evicted. The information, e.g., data, may subsequently be discarded.
Unfortunately, these methods of cache design focus on static techniques instead of adaptive techniques. For example, the length of the stacks in these caches do not adapt, i.e., change in size, to changes in the request stream, i.e., the workload. By designing a cache based on adaptive techniques, the cache hit rate may be improved. Furthermore, these methods do not design a cache that is adaptive based on multiple criteria, e.g., workload, physical characteristics of the network system such as the number of adapters or logical drives in the array of logical drives. Consequently, these methods do not efficiently use memory space thereby providing a need to improve the performance of the cache.
It would therefore be desirable to adaptively allocate memory to support a cache of multiple logical levels enabling the cache to be adaptive to multiple criteria, e.g., physical characteristics of the system, workload, thereby improving the performance of the cache, i.e., improving the cache hit rate.
The problems outlined above may at least in part be solved in some embodiments by logically grouping the stacks associated with a logical drive into a particular logical grouping. A network server, e.g., file server, database server, web server, may be configured to receive a stream of requests from clients in a network system to read from or write to a particular logical drive in an array of logical drives that comprise a Redundant Array of Independent Logical drives (RAID). Each logical drive may be coupled to an adapter, e.g., RAID adapter, which may be coupled to the network server. That is, each adapter may be coupled to one or more logical drives. Each of the logically grouped stacks of the one or more logical drives coupled to an adapter may be logically grouped into a logically grouped stack associated with that adapter. By logically grouping stacks into further logical groupings, memory supporting a partitioned cache of multiple logical levels may be allocated adaptively in response to multiple criteria, e.g., physical characteristics of the system, workload, thereby improving the performance of the cache, i.e., improving the cache hit rate.
In one embodiment of the present invention, a method for reallocating memory space for storing a partitioned cache may comprise the step of allocating a portion of memory to store a plurality of partitions. A partition may refer to a segment of memory space in memory configured to store a stack comprising one or more cache entries where each cache entry may store information, e.g., data. Each stack may be configured to store information in a particular range of logical block addresses associated with a particular logical drive in an array of logical drives that comprise a Redundant Array of Independent Logical drives (RAID). Each particular logical drive may be coupled to a particular adapter, e.g., RAID adapter. That is, an adapter, e.g., RAID adapter, may be coupled to one or more logical drives. A plurality of adapters may then be coupled to a server configured to receive requests to retrieve information, e.g., data, from a particular logical drive. The server may further be configured to retrieve the requested information from the particular logical drive via an adapter coupled to the requested logical drive.
Each stack associated with a particular logical drive may be logically grouped into a logically grouped stack associated with the particular logical drive. As stated above, an adapter, e.g., RAID adapter, may be coupled to one or more logical drives. Subsequently, the logically grouped stacks associated with the one or more logical drives coupled to an adapter may be logically grouped into a logically grouped stack associated with that adapter. As stated above, a plurality of adapters may be coupled to a server configured to receive requests to retrieve information, e.g., data, from a particular logical drive at a particular logical block address.
A determination may be made as to which logically grouped stack associated with each adapter had the highest hit count and which logically grouped stack associated with each adapter had the lowest hit count during a particular interval of time.
The determination as to which logically grouped stack associated with each adapter had the highest hit count and which logically grouped stack associated with each adapter had the lowest hit count during a particular interval of time may comprise the step of tracking the number of cache hits in one or more particular stack positions in each logically grouped stack associated with each particular adapter. The number of cache hits in each of the one or more stack positions tracked in each particular logically grouped stack during a particular interval of time may then be counted. The number of cache hits counted in each of the one or more stack positions tracked in each particular logically grouped stack may then be added. The number of cache hits counted in the one or more stack positions, e.g., last four positions, tracked during a particular interval of time in each particular logically grouped stack may be summed by adders. The output of the adders is inputted to a comparison unit configured to determine which logically grouped stack had the highest hit count in the one or more stack positions tracked and which logically grouped stack had the lowest hit count in the one or more stack positions tracked during a particular period of time.
Upon determining which logically grouped stack had the highest hit count in the one or more stack positions tracked and which logically grouped stack had the lowest hit count in the one or more stack positions tracked during a particular period of time, the memory allocated for storing the logically grouped stack with the highest hit count may gain a block of memory while the memory allocated for storing the logically grouped stack with the lowest hit count may lose a block of memory. These reallocations determined by the comparison unit may be stored in memory.
A determination may then be made as to which logically grouped stack associated with each logical drive coupled to the adapter whose allocated memory is to gain a block of memory is to gain that block of memory, i.e., which logically grouped stack associated with a logical drive has the highest cache hit count. A further determination may be made as to which logically grouped stack associated with each logical drive coupled to the adapter whose allocated memory is to lose a block of memory is to lose that block of memory, i.e., which logically grouped stack associated with a logical drive has the lowest cache hit count. It is noted that even though the following describes which logical drive associated with the adapter determined to gain a block of memory is to gain that block of memory that the following description may apply to determining which logical drive associated with the adapter determined to lose a block of memory is to lose that block of memory.
The determination as to which logically grouped stack associated with each logical drive coupled to the adapter whose allocated memory is to gain a block of memory is to gain that block of memory may comprise the step of tracking the number of cache hits in one or more particular stack positions in each logically grouped stack associated with each logical drive coupled to the adapter whose allocated memory is to gain a block of memory. The number of cache hits in each of the one or more stack positions tracked in each particular logically grouped stack during a particular interval of time may then be counted. The number of cache hits counted in each of the one or more stack positions tracked in each particular logically grouped stack may then be added. The number of cache hits counted in the one or more stack positions, e.g., last four positions, tracked during a particular interval of time in each particular logically grouped stack associated with each logical drive may be summed by adders. The output of the adders is inputted to a comparison unit configured to determine which logically grouped stack associated with each logical drive had the highest hit count in the one or more stack positions tracked.
Upon determining which logically grouped stack associated with each logical drive coupled to the adapter whose allocated memory is to gain a block of memory is to gain that block of memory, the memory allocated for storing the logically grouped stack associated with the particular logical drive with the highest hit count may gain a block of memory. This reallocation determined by the comparison unit may be stored in memory.
A determination may then be made as to which stack associated with the logical drive determined to gain a block of memory is to gain that block of memory, i.e., which logically grouped stack associated with a logical drive has the highest cache hit count. A further determination may be made as to which stack associated with the logical drive determined to lose a block of memory is to lose that block of memory, i.e., which logically grouped stack associated with a logical drive has the lowest cache hit count. It is noted that even though the following describes which stack associated with the logical drive determined to gain a block of memory is to gain that block of memory that the following description may apply to determining which stack associated with the logical drive determined to lose a block of memory is to lose that block of memory.
The determination as to which stack associated with the logical drive determined to gain a block of memory is to gain that block of memory may comprise the step of tracking the number of cache hits in one or more particular stack positions in each stack associated with the logical drive determined to gain a block of memory. The number of cache hits in each of the one or more stack positions tracked in each stack during a particular interval of time may then be counted. The number of cache hits counted in each of the one or more stack positions tracked in each stack may then be added. The number of cache hits counted in the one or more stack positions, e.g., last four positions, tracked during a particular interval of time in each stack associated with the logical drive to gain a block of memory may be summed by adders. The output of the adders is inputted to a comparison unit configured to determine which stack associated with the logical drive to gain a block of memory had the highest hit count in the one or more stack positions tracked.
Upon determining which stack associated with the logical drive to gain a block of memory had the highest hit count in the one or more stack positions tracked during a particular interval of time, the memory allocated for storing the stack with the highest hit count may gain a block of memory. The memory storing the partitioned cache may then be reallocated accordingly. That is, the memory storing the partitioned cache may adaptively reallocate such as by allocating an additional block of memory for the stack with the highest count. The memory storing the partitioned cache may also adaptively reallocate such as by eliminating a block of memory for the stack with the lowest hit count associated with the logical drive coupled to the adapter to lose a block of memory.
Upon reallocating the memory storing the partitioned cache, the memory may be further reallocated by repeating the above determination steps.
The foregoing has outlined rather broadly the features and technical advantages of one or more embodiments of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.